// 随机快速排序，acm练习风格
// 测试链接 : https://www.nowcoder.com/practice/3385982ae71d4a1ca8bf3d03614c0325
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100010;
int arr[MAXN];
int n, first, last;

// 已知arr[l....r]范围上一定有x这个值
// 划分数组 <=x放左边，>x放右边，并且确保划分完成后<=x区域的最后一个数字是x
int partition1(int l, int r, int x)
{
    // a : arr[l....a-1]范围是<=x的区域
    // xi : 记录在<=x的区域上任何一个x的位置，哪一个都可以
    int a = l, xi = 0;
    for(int i = l; i <= r; ++i)
    {
        if(arr[i] <= x)
        {
            swap(arr[i], arr[a]);
            if(arr[a] == x)
            {
                xi = a;
            }
            ++a;
        }
    }
    swap(arr[xi], arr[a - 1]);
    return a - 1;
}

// 随机快速排序经典版(不推荐)
void quickSort1(int l, int r)
{
    if(l >= r) return;

    // 随机这一下，常数时间比较大
    // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
    // l......r 随机选一个位置，x这个值，做划分
    int x = arr[rand() % (r - l + 1) + l];
    int mid = partition1(l, r, x);
    quickSort1(l, mid - 1);
    quickSort1(mid + 1, r);
}

// 荷兰国旗问题
void partition2(int l, int r, int x)
{
    first = l, last = r;
    int i = l;
    while(i <= last)
    {
        if(arr[i] == x) ++i;
        else if(arr[i] < x) swap(arr[first++], arr[i++]);
        else swap(arr[last--], arr[i]);
    }
}

// 随机快速排序改进版(推荐)
void quickSort2(int l, int r)
{
    if(l >= r) return;
    // 随机这一下，常数时间比较大
    // 但只有这一下随机，才能在概率上把快速排序的时间复杂度收敛到O(n * logn)
    int x = arr[rand() % (r - l + 1) + l];
    partition2(l, r, x);
    // 为了防止底层的递归过程覆盖全局变量
    // 这里用临时变量记录first、last
    int left = first, right = last;
    quickSort2(l, left - 1);
    quickSort2(right + 1, r);
}

int main()
{
    srand(time(nullptr));
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);
    quickSort2(0, n - 1);
    for(int i = 0; i < n; ++i) printf("%d ", arr[i]);
    printf("\n");

    return 0;
}